//一团浆糊，想偷个懒把前面树的直接复制过来，结果把树和队列的搞混了，不知道咋改了，自己写个头文件封装一下吧
//需要的是两个模板类，我是不是应该用下typedef
#include <iostream>
using namespace std;

template <class N>
struct Node
{
	N data;
	Node<N>* next;
	//Node() {};
	Node(N val) :data(val), next(NULL) {};  
};

template <class T>
struct TNode
{
	T data;
	TNode<T>* left;
	TNode<T>* right;
	TNode(T val):data(val),left(NULL),right(NULL){};
};

template <class N>
class Queue
{

	Node<N>* head;
	Node<N>* tail;
public:
	Queue(Node<N>* t) :head(t), tail(t) {};
	Queue() :head(NULL), tail(NULL) {};
	~Queue() { delete head; head = NULL; delete tail; tail = NULL; };
	void EnQueue(N val);
	void DeQueue();
	bool IsEmpty();
	void Print();
	Node<N>* QueueHeadVal();
};
template <class N>
void Queue<T>::EnQueue(N val) {
	
	if (val == NULL) {
		Node<N>* tmp = new Node<N>(val);
		head = tmp;
		tail = tmp;
	}
	else {
		Node<N>* tmp = new Node<N>(val);
		tail->next = tmp;
		tail = tmp;
	}
}
template <class N>
void Queue<N>::DeQueue() {
	if (this->head == NULL) {
		return;
	}
	else {
		Node<N>* tmp = head;
		head = head->next;
		delete tmp;
		tmp = NULL;
	}
}
template <class N>
bool Queue<N>::IsEmpty() {
	return this == NULL;
}
template <class N>
void Queue<N>::Print() {
	Node<N>* cur = this->head;
	while (cur != NULL ) {
		cout << cur->data << endl;
		cur = cur->next;
	}
}
template <class N>
Node<N>* Queue<N>::QueueHeadVal() {
	return this->head;
}


template<class T>
class BTree
{
	TNode<T>* tnode;
public:
	BTree():tnode(NULL){};
	//BTree(TNode<T>* t):tnode(t){};
	~BTree();
	void Add(T t,TNode<T>* tn){
		TNode<T>* tmp = new TNode<T>(t);
		if(tn == NULL){
			tn = tmp;
		}
		else{
			if(t < tn->data){
				if(tn->left == NULL){
					tn->left = tmp;
				}
				else{
					Add(t,tn->left);
				}
			}
			else{
				if(tn->right == NULL){
					tn->right = tmp;
				}
				else{
					Add(t,tn->right);
				}
			}
		}
	};
	void BTreePrint(TNode<T>* tn){
		if(tn){
			cout<<tn->data<<endl;
			BTreePrint(tn->left);
			BTreePrint(tn->right);
		}
	}; 
	
};
template <class T>
void BFSTreeTravelQueue(TNode<T>* t){
	Queue<TNode<T>*>* q = new Queue<TNode<T>*>();
	q->EnQueue(t);
	while(!q->IsEmpty()){
		Node<TNode<T>*>* cur = q->QueueHeadVal();
		cout<<cur->data<<endl;
		q->DeQueue();
		q->EnQueue(cur->data->left);
		q->EnQueue(cur->data->right);
	}

}
int main(int argc, char const *argv[])
{
	double arr[10] = { 3,2,1,4,6,5,0,9,7,8 };
	// Queue<double>* deq = new Queue<double>();
	// for (int i = 0; i < 10; i++) {
	// 		deq->EnQueue(arr[i]);
	// }
	// deq->Print();
	// cout<<endl;
	// for(int i = 0;i < 4;i++){
	// 	cout<<deq->QueueHeadVal()<<endl;
	// 	deq->DeQueue();
	// }
	TNode<double>* root = NULL;
	BTree<double>* bbt = NULL;
	for(int i = 0;i < 10;i++){
		if(i == 0){
			root = new TNode<double>(arr[i]);
		}
		else{
			bbt->Add(arr[i],root);
		}
	}
	//bbt->BTreePrint(root);
	BFSTreeTravelQueue(root);
	return 0;
}
